package top.datacluster.basic.algorithm.leetcode.link;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Stack;

/**
 * 445. 两数相加 II
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 *
 *
 * 进阶：
 *
 * 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
 *
 *
 *
 * 示例：
 *
 * 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 8 -> 0 -> 7
 */
public class LeetCode445 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode temp = l1;
        Stack<Integer> first = new Stack<>();
        while (temp != null){
            first.push(temp.val);
            temp = temp.next;
        }
        temp = l2;
        Stack<Integer> second = new Stack<>();
        while (temp != null) {
            second.push(temp.val);
            temp = temp.next;
        }
        ListNode head = new ListNode(0);
        int label = 0;
        while (!first.isEmpty() && !second.isEmpty()) {
            ListNode l = new ListNode((first.peek() + second.peek()+ label) % 10 );
            label = (first.pop() + second.pop()) / 10;
            l.next = head.next;
            head.next = l;
        }
        while (!first.isEmpty()){
            ListNode l = new ListNode((first.peek() + label) % 10);
            label = (first.pop() + label) / 10;
            l.next = head.next;
            head.next = l;
        }
        while (!second.isEmpty()){
            ListNode l = new ListNode((second.peek() + label) % 10);
            label = (second.pop() + label) / 10;
            l.next = head.next;
            head.next = l;
        }
        if (label == 1){
            ListNode l = new ListNode(label);
            l.next = head.next;
            head.next = l;
        }

        return head.next;

    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(3);
        ListNode l2 = new ListNode(9);
        ListNode l3 = new ListNode(9);
        ListNode l4 = new ListNode(9);
        ListNode l5 = new ListNode(9);
        ListNode l6 = new ListNode(9);
        ListNode l7 = new ListNode(9);
        ListNode l9 = new ListNode(9);
        ListNode l10 = new ListNode(9);
        ListNode l11 = new ListNode(9);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = l6;
        l6.next = l7;
        l7.next = l9;
        l9.next = l10;
        l10.next = l11;
        ListNode l8 = new ListNode(7);
        new LeetCode445().addTwoNumbers(l1, l8);

    }

}
